package SortSummary;

/*
*   堆排序
*       时间复杂度：O(nlogN)
*       空间复杂度：O(1)
*       稳定性：不稳定
* */

class HeapSort {
    static void heapSort(int[] nums){
        int heapSize = nums.length;

        //heapInsert做大根堆
        /*for(int i=0;i<nums.length;i++){
            heapInsert(nums,i);
            heapSize++;
        }*/

        //heapify做大根堆
        for(int i=nums.length-1;i>=0;i--){
            heapify(nums,i,nums.length);
        }

        while(heapSize>0){
            swap(nums,0,--heapSize);
            heapify(nums,0,heapSize);
        }
    }

    //某个数在index位置上，往下移动
    static void heapify(int[] nums,int index,int heapSize){
        while(index*2+1 < heapSize){
            int leftChild = index*2+1;
            int rightChild = leftChild+1;
            int largest = rightChild<heapSize && nums[leftChild]<nums[rightChild]?rightChild:leftChild;
            largest = nums[index]<nums[largest]?largest:index;
            swap(nums,largest,index);
            if(index == largest){
                break;
            }
            index = largest;
        }
    }

    //某个数在index位置上，向上移动
    static void heapInsert(int[] nums,int index){
        while(nums[index] > nums[(index-1)/2]){
            swap(nums,index,(index-1)/2);
            index = (index-1)/2;
        }
    }

    static void swap(int[] nums,int i,int j){
        int n = nums[i];
        nums[i] = nums[j];
        nums[j] = n;
    }

    /*public static void main(String[] args) {
        int[] nums = new int[]{7,2,3,8,1,0,9};
        heapSort(nums);
        for(int n:nums){
            System.out.println(n);
        }
    }*/
}
